//#define _CRT_SECURE_NO_WARNINGS
//#include <iostream>
//#include <string>
//#include <map>
//#include <queue>
//#include <algorithm>
//using namespace std;
//
//int main() {
//    int num = 0;
//    cin >> num;
//    int arr[27] = { 0 };
//    while (num--)
//    {
//        char c = '0';
//        cin >> c;
//        arr[c - 'a']++;
//    }
//    map<int, char> mp;
//    for (int i = 0; i < 26; i++)
//    {
//        mp.insert(make_pair(arr[i], i + 'a'));
//    }
//    char before = '0';
//    string s;
//    while (!mp.empty())
//    {
//        if (mp.end()->second != before && mp.end()->first > 0)
//        {
//            s.push_back(mp.end()->second);
//            int a = mp.end()->first - 1;
//            before = mp.end()->second;
//            mp.erase(before);
//            mp[a] = before;
//        }
//        else
//        {
//            int a = mp.end()->first;
//            char c = before;
//            mp.erase(before);
//            s.push_back(mp.end()->second);
//            before = mp.end()->second;
//            int b = mp.end()->first;
//            mp[a] = c;
//        }
//    }
//    
//    return 0;
//}


//int main() {
//    int k = 0;
//    cin >> k;
//    while (k--)
//    {
//        long long num = 0, score = 0;
//        cin >> num >> score;
//        long long times = 0, ret = 0;
//        while (num--)
//        {
//            char c = '0';
//            cin >> c;
//            if (c == 'W')
//            {
//                ret++;
//                times++;
//                if (times == 3)
//                {
//                    ret += score - 1;
//                    times = 0;
//                }
//            }
//            else {
//                ret--;
//                times = 0;
//            }
//        }
//        cout << ret << endl;
//    }
//    return 0;
//}